Threshold arrays have been used for years to accomplish halftoning for image forming equipment, such as printers. Modem printers generally use a threshold array in a tiling manner to halftone a particular square or rectangular portion of an image bitmap that is to be printed, and then move the threshold array to the next position as if placing a new tile over the bitmap in an adjacent location. Video displays also can operate using tiled threshold arrays. Threshold arrays include array elements that have numeric values that range from the lightest gray scale shade to the darkest gray scale shade. As the light intensity (or a particular color intensity) increases, a greater number of pixels will be illuminated in a display device such as a liquid crystal display, or conversely a fewer number of dots will be printed in the case of a printer as the output device. This is accomplished by comparing the actual pixel intensity values against the array element numeric values. For example, all dots will be printed for threshold levels at array element locations that have a numeric value less than the dot intensities of the input image information.
The numeric values of the array elements for threshold arrays in conventional printers are normally integer values that define a plurality of gray levels, and the most typical range of numeric values is from 0 through 255, which are represented by 8-bit binary numbers. Since 8-bit linear or unadjusted threshold arrays produce printed responses that typically do not match the desired linear human perceptual response, it has been common for most printers to provide adjusted (or corrected) threshold arrays for each color that can be printed by that particular print engine. In color printers, for example, this implies that there would be a minimum of three different adjusted threshold arrays for the “ordinary” colors cyan, magenta, and yellow, and further, many color printers also provide black ink, thereby requiring a fourth adjusted threshold array. (Some printers may provide a single threshold array to be used for all colors, but the visual results are not pleasing.) Such adjusted threshold arrays may have array elements of integer numeric values or, to achieve greater precision, the numeric values could each be represented by a floating point number. Floating point values will require, of course, much more storage space in the memory system of a printer than the use of integer values. One main reason that 8-bit integer values are typically used for the gray level representations is that standard memory devices provide “chunks” of memory in bytes, which each comprise a set of 8 bits.
Early printers may have used unadjusted threshold arrays to produce their final printed outputs, however, such printers usually lose tone levels, and at best exhibit crude approximations to the desired perceptual tone levels. While some print engines may produce reasonable perceptual responses by use of unadjusted threshold arrays, that is not the general case, and adjusted threshold arrays are much more common.
To develop a linearized halftone screen, it is common to start with a grid of equal proportions of the numbers between one (1) and the maximum value, and then print squares representing each of the tone levels. The printed squares can be then measured with respect to the parameter that is desired to be linearized. The series of measured values can then be assembled and analyzed to form an adjusted (or corrected) halftone screen or threshold array that is linear. The new screen or array is formed for a given paper type, color plane, printing mechanism, etc., and usually is stored in ROM to be used when printing.
The maximum value of the equal proportions used in generating the unadjusted threshold array may not be the same as the maximum tone level. However, the maximum values of the adjusted screen or threshold array and the tone level must be the same. It very rarely occurs that using an unadjusted screen yields a set of equally visually spaced discernible intensity levels, which is the property of a “perfect” halftone screen. Thus, it is necessary to “correct” (or adjust) this screen.
In correcting the screen (or threshold array), the first thing to be achieved is determining a set of distinct intensity levels, as many as the number of tone levels (i.e., gray scale levels in many cases). These intensity levels must be analyzed and modified so that they are as visually distinct as possible. This usually is done by linearizing the screens in L* space. Historically, correction (or adjustment) of the screens or threshold arrays has been done using one of two different methods. The first method is referred to as the “array mapping” method, which stores a one-dimensional array that maps each of the possible values in the uncorrected (or unadjusted) screen or threshold array to the appropriate value in the corrected (or adjusted) screen or threshold array. Each of the values in the unadjusted screen or threshold array is used as an index to the array map, and the adjusted screen or threshold array is formed therefrom. This method saves memory space, but can be restrictive concerning the number of dots that must be placed on the page for different tone levels. For example, if the uncorrected (or unadjusted) screen or array has dimensions of 128×128, and if there are 256 tone levels, each tone level must contain 64 more dots than the previous level, assuming that the unadjusted screen or array contains equal proportions of each value (which must be true if it is to be used as a base to transition to adjusted (or corrected) arrays).
Since being restricted to adding a fixed number of dots at each level reduces the number of distinct intensity levels, accuracy will suffer. This accuracy problem can be alleviated by increasing the range of values in the unadjusted screen or array until the maximum number of unique levels is obtained. Unfortunately, this also increases the size of both the one-dimensional arrays and the unadjusted screens, which are both stored in the printer when using the array mapping method. The size of the one-dimensional arrays increases proportionally with the bit size of the uncorrected (or unadjusted) screens or threshold arrays.
The second historical correcting method is called the “complete storage” method. This performs the complete correction of the threshold arrays offline, and all of the adjusted (or corrected) threshold arrays are stored in the ROM of the printer. No correction takes place at run time. This method requires a large amount of memory space; however, it's advantage it that the adjusted (or corrected) threshold arrays can be manipulated as necessary to obtain the greatest number of visually discernible intensity levels, since all correction is done offline (i.e., at the factory). Increase of accuracy does not mean an increase of the memory space required for storage. Nevertheless, the memory storage space is quite large for any threshold arrays of meaningful precision.
In printers that provide adjusted threshold arrays, a separate transfer function is typically determined for each color that can be printed, and additionally, for each type of print media that will be printed on. The benefits of using adjusted threshold arrays include assuring that there will be 256 unique tone levels (e.g., for 8-bit integer gray levels), and further, to produce tone levels as close as possible to each desired perceptual level. However, a separate array must be generated for each combination of color and type of paper, and therefore, a large amount of memory is required to store each of the separate, adjusted threshold arrays. More detailed examples of the memory requirements are provided hereinbelow.
Once the printer's actual response curve is known, it is possible to apply a transfer function to correct or adjust the data so that a perceptually appropriate gray level will be printed for a corresponding lightness level L*. In the prior art, such transfer functions have normally taken the form of a correction factor that is added to the gray level for a particular lightness L* value. In essence, the printer's response curve (such as curve 102 on FIG. 2) is compared to the ideal target response (such as line 100 on FIG. 2), and the deviation at all important points is calculated. Once this deviation is known, it is a simple matter to create a mirror-image curve on the opposite side of the ideal target response line 100, and this mirror-image curve can be added to the actual printer response curve (such as curve 102) and an average taken, which then will provide the adjusted (or corrected) response that will have the appearance of the ideal target response line 100.
While the prior art methodology works well for many conventional printers, a large amount of memory storage space is required to store the corrected threshold array that is generated or derived by applying the mirror image transfer function curve to correct for the printer's non-linear actual response curve. Moreover, since correcting for each printer color and print media type will lead to a large number of possible combinations, it has been common in the prior art for the conventional printers to store a large number of such adjusted threshold arrays in their non-volatile memory, such as in the printer's ROM, thereby requiring substantial amounts of memory space.
Since threshold arrays provide an extremely fast way to halftone an image, various types of halftoning techniques have been developed that all use threshold arrays, including cluster-dot ordered dithering (known as “classical” screening), dispersed-dot ordered dithering (known as “Bayer” screening), dispersed-dot unordered dithering (known as stochastic screening), or another form of stochastic screening, using cluster-dot unordered dithering. For printers that must quickly process image data for an incoming print job, this extremely fast method using threshold arrays so far seems to be the optimum method to halftone various types of images. It would be very beneficial to further streamline the process of providing corrected threshold arrays, especially when that process can also save memory space within the printer's memory circuits.